package com.atguigu.main.search;

/**
 * @author ：剧情再美终是戏
 * @description： 获取数组中第 k 个大的数据
 * @mail : 13286520398@163.com
 * @date ：Created in 2020/2/28 20:50
 * @modified By：
 * @version: 1.0$
 */
public class FindKthLargest {
    public static void main(String[] args) {
        int[] arr = {2, 8, 7, 1, 3, 5, 6, 4};
        System.out.println(findKthLargest(arr, 3, 0, 7));
    }


    private static int findKthLargest(int[] arr, int k, int l, int r) {
        // 计算哨兵的位置
        int p = getPartition(arr, l, r);
        // 如果确定的哨兵的位置等于 k, 直接返回 k -1 就是下标，从 0 开始
        if (k - 1 == p) {
            return arr[p];
        } else if (k - 1 > p) { // 如果 k 大于这个中位数，就说明这个 k 值在中位数的右边， 递归查询中位数右边的集合
            return findKthLargest(arr, k, p + 1, r);
        } else { // 如果 k 小于这个中位数，就说明这个 k 值在中位数的左边，递归查询中位数的左边的集合
            return findKthLargest(arr, k, l, p - 1);
        }
    }

    private static int getPartition(int[] arr, int l, int r) {
        int x = arr[r];
        int i = l - 1;
        for (int j = 0; j < r; j++) {
            if (arr[j] >= x) {
                i += 1;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, r);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
